package com.vilynn.learning.sort;

/**
 * Created by weilin.wang on 2018/3/3
 */
public class QuickSort implements SortService {
    @Override
    public int[] sort(int[] arrs) {
        quickSort(arrs, 0, arrs.length-1);
        return arrs;
    }

    private void quickSort(int[] arrs, int low, int high) {
        if(low < high){
            int partion = partion(arrs, low, high);
            quickSort(arrs, low, partion);
            quickSort(arrs, partion, high);
        }
    }

    private int partion(int[] arrs, int low, int high) {
        for(int i = low, j = high;i<arrs.length && j >= 0;){
            if(arrs[i] > arrs[low] && arrs[j] < arrs[low]){
                int temp = arrs[low];
                arrs[low] = arrs[j];
                arrs[j] = temp;
                return j;
            }
            if(arrs[i] < arrs[low]){
                i++;
            }
            if(arrs[j] > arrs[low]){
                j--;
            }
        }
        return low;
    }
}